public class MySingleList {
    //定义一个内部类
    class Node{//结点
        public int val;//存储数据
        public Node next;//存储下一个节点的地址

        public Node(int val) {
            this.val  = val;
        }
    }
    public Node head;//代表当前链表的头节点的引用，head头节点，他还是结点，所以还是用Node作为类型

    public void createLink(){
        Node node1 = new Node(12);
        Node node2 = new Node(13);
        Node node3 = new Node(14);
        Node node4 = new Node(15);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;

    }
    /*
     *遍历列表
     * */
    public void display(){
        Node cur = head;//将head的值传给cur,让cur代替head来实现代跑，那么每次遍历完链表后，下次遍历可以回到开头
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();//换行
    }
    /*
    *在链表当中查找是否包含关键字key
    *
    * */
    public boolean contains(int key){
        Node cur = head;//通过cur带跑，遍历链表
        while(cur != null){//结束条件，当将链表每个元素都便利完成，代码结束
            if(cur.val == key){//判断cur结点的数据是否和查找的相同。
                return true;
            }
            cur = cur.next;//不同继续向后序结点遍历
        }
        return false;//遍历完成之后没有该关键字，返回false.
    }
    /*
    * 得到链表的长度
    * */
    public int size(){
        int count = 0;//定义count用来计数
        Node cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
     /*
     * 头插法
     * */
    public void addFirst(int data){
        Node node = new Node(data);//实例化结点
        node.next = head;
        head = node;
    }
    /*
    * 尾插法
    * */
    public void addLast(int data){
        Node node = new Node(data);
        if(head == null){//判断链表是否为空，若为空，插入时，直接让其等于新增的结点
            head = node;
            return;
        }
        Node cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }
    /*
    * 任意位置插入
    * */
    public void addIndex(int index,int data)throws IndexOutOfException{
        checkIndex(index);
        if(index == 0){//如果在链表的开头插入
            addFirst(data);//调用头插法
            return;
        }
        if(index == size()){//如果在链表的结尾插入
            addLast(data);//调用尾插法
            return;
        }
        Node cur = findIndexSubOne(index);
        Node node = new Node(data);
        //将结点插入链表之后，先要和插入结点的后一个结点建立联系。
        node.next = cur.next;//这里的cur.next域node.next表示的都是cur的地址域
        cur.next = node;

    }
    /*
    * 找到index-1位置的结点的地址
    * */
    private Node findIndexSubOne(int index){
        Node cur = head;
        int count = 0;
        while(count != index -1){//判断是否为index前一个位置的结点
            cur = cur.next;//不是，向后移动，找index位置的前一个位置的结点
            count++;
        }
        return cur;
    }
    private void checkIndex(int index) throws IndexOutOfException{
        if(index < 0 || index > size()){
            throw new IndexOutOfException("Index位置不合法");
        }
    }
    /*
    * 删除第一次出现关键字为key的节点
    * */
    public void remove(int key){
        if(head.val == key){
            head = head.next;
            return;
        }
        Node cur = searchPrev(key);
        if(cur == null){//这里的判断，表示没有要删除的节点
            return;
        }
        Node del = cur.next;//记录要删除的节点
        cur.next = del.next;
    }
    /*
    * 找到关键字的前一个结点
    * */
    private Node searchPrev(int key){
        if(head == null){//这个判断是必要的，没有这个判断，在进行下面的操作时，会报空指针异常
            return null;//说明链表当中一个节点都没有
        }
        Node cur = head;
        while(cur.next != null){//当cur.next等于null时，说明这个链表当中没有要找的关键字
            if(cur.next.val == key){//cur将来是key的前驱节点。
                return cur;
            }
            cur = cur.next;
        }
        return null;//代表没有你要删除的节点
    }
    /*
    * 删除所有值为key的节点
    * */
    public void removeAllKey(int key){
        if(head == null){
            return;
        }
//        while(head.val == key){
//            head = head.next;
//        }
        Node prev = head;
        Node cur = head.next;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
            if(head.val == key){
                head = head.next;
            }
        }
    }
    /*
    * 保证链表当中的所有节点都可以被回收
    * */
    public void clear(){
        head = null;//会将链表的每个节点都置为空
    }
}
